package main.Q1201_1300;

import java.util.HashMap;
import java.util.Map;

public class Q1211_1220 {
    public static void main(String[] args) {
        System.out.println("Question1211：");
        System.out.println("Question1211：");
        System.out.println("Question1213：");
        System.out.println("Question1214：");
        System.out.println("Question1215：");
        System.out.println("Question1216：");
        System.out.println("Question1217：");
        System.out.println("Question1218：最长定差子序列");
        System.out.println("Question1219：黄金矿工");
        System.out.println("Question1220：");
    }
}

class Question1218 {
    public int longestSubsequence(int[] arr, int difference) {
        int result = 1;
        if (arr.length == 1) return result;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int temp = 1;
            if (map.containsKey(arr[i] - difference)) {
                temp = map.get(arr[i] - difference);
                temp++;
                map.put(arr[i], temp);
            } else {
                map.put(arr[i], temp);
            }
            result = Math.max(result, temp);
        }
        return result;
    }
}

class Question1219 {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] grid;
    int m, n;
    int result = 0;

    public int getMaximumGold(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] != 0) {
                    process(i, j, 0);
                }
            }
        }
        return result;
    }

    public void process(int x, int y, int gold) {
        gold += grid[x][y];
        result = Math.max(result, gold);
        int rec = grid[x][y];
        grid[x][y] = 0;
        for (int d = 0; d < 4; ++d) {
            int nx = x + dirs[d][0];
            int ny = y + dirs[d][1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
                process(nx, ny, gold);
            }
        }
        grid[x][y] = rec;
    }
}